package com.yvon.service.demo.algorithm.offer;

import java.util.Stack;

/**
 * 用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的 元素为 int 类型。
 * https://doocs.gitee.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9809.%20%E7%94%A8%E4%B8%A4%E4%B8%AA%E6%A0%88%E5%AE%9E%E7%8E%B0%E9%98%9F%E5%88%97/README
 */
public class P09 {
    public static void main(String[] args) {
        Solution stackqueue =new P09().new Solution();
        int[] arr = {1,2,3,4,5,6};
        for(int i=0;i<arr.length;i++){
            stackqueue.push(arr[i]);
        }

        for(int i=0;i<arr.length;i++){
            System.out.println(stackqueue.pop());
        }
    }

    /**
     * 由于队列是先进先出的，而栈是先进后出的，故可以用2个栈实现队列的入、出队功能，
     * 队列的入队功能与栈的一样，出队时，先将第一个栈中的元素全部弹出，并倒入到第二个栈中，
     * 将第二个栈中栈顶元素弹出，并将stack2中剩下的元素倒回到stack1中，即实现一次出队。
     */
    class Solution {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();

        public void push(int node) {
            stack1.push(node);
        }

        public int pop() {
            if (stack1.isEmpty() && stack2.isEmpty()) {
                return -1;
            }
            if (stack2.isEmpty()) {
                while (!stack1.isEmpty()) {
                    stack2.push(stack1.pop());
                }
            }
            return stack2.pop();
        }
    }
}
